A computer network is a geographically distributed collection of interconnected subnetworks for transporting data between nodes, such as computers. A local area network (LAN) is an example of such a subnetwork. The network's topology is defined by an arrangement of client nodes that communicate with one another, typically through one or more intermediate network nodes, such as a router or switch. As used herein, a client node is an endstation node that is configured to originate or terminate communications over the network. In contrast, an intermediate network node is a node that facilitates routing data between client nodes. Communications between nodes are typically effected by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables the client nodes and intermediate nodes to efficiently route the packet through the computer network. Often, a packet's network headers include at least a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
The data-link header provides information for transmitting the packet over a particular physical link (i.e., a communication medium), such as a point-to-point link, Ethernet link, wireless link, optical link, etc. To that end, the data-link header may specify a pair of “source” and “destination” network interfaces that are connected by the physical link. A network interface contains the mechanical, electrical and signaling circuitry and logic used to couple a network node to one or more physical links. A network interface is often associated with a hardware-specific address, known as a media access control (MAC) address. Accordingly, the source and destination network interfaces in the data-link header are typically represented as source and destination MAC addresses. The data-link header may also store flow control, frame synchronization and error checking information used to manage data transmissions over the physical link.
The internetwork header provides information defining the packet's logical path (or “virtual circuit”) through the computer network. Notably, the path may span multiple physical links. The internetwork header may be formatted according to the Internet Protocol (IP), which specifies IP addresses of both a source and destination node at the end points of the logical path. Thus, the packet may “hop” from node to node along its logical path until it reaches the client node assigned to the destination IP address stored in the packet's internetwork header. After each hop, the source and destination MAC addresses in the packet's data-link header may be updated, as necessary. However, the source and destination IP addresses typically remain unchanged as the packet is transferred from link to link in the network.
The transport header provides information for ensuring that the packet is reliably transmitted from the source node to the destination node. The transport header typically includes, among other things, source and destination port numbers that respectively identify particular software applications executing in the source and destination nodes. More specifically, the packet is generated in the source node by the application assigned to the source port number. Then, the packet is forwarded to the destination node and directed to the application assigned to the destination port number. The transport header also may include error-checking information (i.e., a checksum) and other data-flow control information. For instance, in connection-oriented transport protocols such as the Transmission Control Protocol (TCP), the transport header may store sequencing information that indicates the packet's relative position in a transmitted stream of data packets.
As used herein, a dataflow is a stream of data packets that is communicated from a source node to a destination node. Each packet in the flow satisfies a set of predetermined criteria, e.g., based on the packet's contents, size or relative position (i.e., temporal or spatial) in the data flow. An intermediate network node may be configured to perform “flow-based” routing operations so as to route each packet in a data flow in the same manner. The intermediate node typically receives data packets in the flow and forwards the packets in accordance with predetermined routing information that is distributed using a protocol, such as the Open Shortest Path First (OSPF) protocol. Because each packet in the flow is addressed to the same destination node, the intermediate node need only perform one forwarding decision for the entire data flow, e.g., based on the first packet received in the flow. Thereafter, the intermediate node forwards packets in the data flow based on the flow's previously determined routing information (i.e., adjacency information). In this way, the intermediate node consumes fewer resources, such as processor bandwidth and processing time, than if it performed a separate forwarding decision for every packet in the data flow.
In practice, the intermediate network node may implement a hash table which stores packet-related information used to classify received packets into their corresponding data flows. The hash table is typically organized as a table of linked lists, where each list may be indexed by the result of applying a conventional hash function to “signature” information. In this context, a signature is a set of values that remain constant for every packet in a data flow. For example, assume each packet in a first data flow stores the same pair of source and destination IP address values. In this case, a signature for the first data flow may be generated based on the values of these source and destination IP addresses. Likewise, a different signature may be generated for a second data flow whose packets store a different set of source and destination IP addresses than packets in the first data flow. Of course, those skilled in the art will appreciate that a data flow's signature information is not limited to IP addresses and may include other information, such as TCP port numbers, IP version numbers and so forth.
Each linked list in the hash table contains one or more entries, and each linked-list entry stores information corresponding to a particular data flow. Such information may include, inter alia, the data flow's associated signature information and a data-flow identifier (“flow ID”). The flow ID identifies the particular data flow and also may be used to locate routing information associated with the data flow. To that end, the intermediate network node may maintain a data structure that maps flow ID values to the memory locations of their corresponding routing information, e.g., stored in the node's local or internal memory. Alternatively, the flow ID values may directly incorporate the memory locations of their data flows' routing information.
When a packet is received by the intermediate network node, signature information is extracted from the packet's network headers and hashed using a conventional hash function, such as a cyclic redundancy check (CRC) function. The resultant hash value is used to index a hash-table entry which, in turn, references a linked list. Entries in the linked list are accessed sequentially until a “matching” entry is found storing the extracted signature. When a matching linked-list entry is located, the entry's stored flow ID value is used to associate the received packet with a data flow and the packet is routed in accordance with that flow.
The intermediate network node typically receives a large number of data flows from various sources, including client nodes and other intermediate nodes. Each source may be responsible for establishing one or more data flows with the intermediate node. To optimize use of its processing bandwidth, the intermediate node may process the received flows on a prioritized basis. That is, as packets are received at the intermediate node, they are identified as belonging to, e.g., a high or low priority data flow. Packets in the high-priority flow may be processed by the intermediate node in advance of the low-priority packets, even if the low-priority packets were received before the high-priority packets.
Denial-of-service (DoS) attacks have become fairly common techniques for disabling access to resources and/or services in an intermediate network node. A DoS attack corresponds to a data flow of “malicious” packets which, when processed by the intermediate network node, deprive non-malicious packets (i.e., non-DoS packets) access to certain resources and/or services in the node. The DoS packets may be sent from a single source or may be coordinated among a plurality of sources. This latter case is often referred to as a distributed DoS (DDOS) attack. For example, a computer hacker may launch a DDoS attack through a multitude of compromised endstations that transmit data packets to a target intermediate node, thereby overwhelming the intermediate node's processing bandwidth.
DoS attacks typically involve sending large quantities of a specific type of network traffic, such as packets formatted in accordance with the Internet Control Message Protocol (ICMP) or the Internet Group Management Protocol (IGMP), to the intermediate network node. In many cases, the DoS packets are pre-pended by a complex arrangement of network headers. Thus, the targeted intermediate network node becomes overburdened not only by the large quantity of received DoS packets, but also by the consumption of resources required to process them. Since the intermediate node's resources become overly consumed processing these malicious packets, other non-malicious packets sent to the intermediate node are often dropped or discarded. Accordingly, different types of intermediate network nodes attempt to prevent DoS attacks in various ways.
The high-end “core” routers and switches typically have enough processing bandwidth to process both malicious DoS packets as well as non-malicious packets. In this context, the high-end routers and switches are designed to handle large amounts of network traffic, e.g., on a network “backbone.” Consequently, the malicious packets can be processed at the rate at which they are received, i.e., at “line” rate. These high-end intermediate nodes thus rely primarily on hardware forwarding solutions that cannot become over-subscribed while identifying and removing the malicious DoS packets. As a result, a substantial portion of processing bandwidth in the central processing unit(s) (CPU) executing the software may be consumed identifying and removing DoS packets. Another disadvantage of this solution is that the routing or switching software becomes more complex by the inclusion of code for filtering the DoS packets from the received data flows.
The “mid-range” routers and switches, unlike their high-end counterparts, typically become oversubscribed as a result of a DoS attack. These intermediate nodes are usually enterprise or LAN routers/switches that manage a relatively large number of data flows. In order to identify and remove DoS traffic (i.e., data packets), the mid-range routers and switches typically utilize software executing on a centralized CPU or on a network processor supporting a general-purpose CPU. Like the software in the high-end routers and switches, the software in the mid-range routers and switches consumes an excessive amount of processing bandwidth and complexity for thwarting the DoS attack.
Hardware support for prioritization of ingress traffic is sometimes implemented in the mid-range routers and switches when the “problem” DoS traffic can be filtered and put on a low-priority queue serviced by the software. However, because the number of malicious packets typically becomes exorbitant during the DoS attack, the low-priority queue usually fills and is therefore tail-dropped, dropping both the malicious DoS traffic as well as non-malicious low-priority traffic. Furthermore, the hardware filtering is typically implemented as a simple table lookup on data link (layer 2) or internetwork (layer 3) information contained in the received data packets. The table lookup may be performed using a content addressable memory (CAM), such as a ternary CAM (TCAM). If the DoS attack traffic arrives via a complicated encapsulation, this table-based filtering cannot support these encapsulations and the DoS traffic is then forwarded to the software executing on the CPU. As a result, the hardware support does not prevent the CPU from being burdened with processing the DoS traffic.
The low-end “access” routers and switches are typically single CPU systems that process a relatively small amount of network traffic and are therefore more susceptible to a DoS attack than the above-noted mid-range and high-end intermediate network nodes. There is only one CPU in the low-end routers and switches, so CPU bandwidth is typically not consumed pre-processing or prioritizing in-coming data packets. Such preprocessing would require the software executing on the CPU to process each received packet twice (prioritize and route) thus consuming an unacceptable amount of processing resources. Therefore, the low-end routers and switches usually only filter received data packets (if at all) using simple lookup tables or TCAMs that are not able to identify complex DoS packet encapsulations.
There is generally a need for an intermediate network node that can identify and remove DoS traffic without consuming an excessive amount of processing resources or bandwidth in the node. Further, the intermediate node should identify and remove DoS traffic having encapsulations of any arbitrary complexity. In addition, the malicious DoS packets should be removed from the intermediate node without affecting the processing of non-malicious packets, such as low-priority non-malicious packets.